package cn.edu.xjtu.work.isValidParentheses;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 20. 有效的括号
 * 
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 
 * 有效字符串需满足： 1. 左括号必须用相同类型的右括号闭合。 2.左括号必须以正确的顺序闭合。
 */
public class Solution {
  public static void main(String[] args) {
    String s = "";
    System.out.println(isValid(s));
  }

  public static boolean isValid(String s) {
    if (s == null) {
      return false;
    }
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');

    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
      char ch = s.charAt(i);
      if (map.containsKey(ch)) {
        stack.push(ch);
      } else {
        if (stack.isEmpty() || map.get(stack.pop()) != ch)
          return false;
      }
    }
    if (stack.isEmpty()) {
      return true;
    } else {
      return false;
    }

  }
}
